//递归：
#include <stdio.h>

int Fib(int n)
{
    if (n <= 2)
    {
        return 1;
    }
    else
    {
        return Fib(n - 1) + Fib(n - 2);
    }
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = Fib(n);
    printf("%d", ret);
    return 0;
}
//如果用递归的方法，会造成严重的时间浪费，效率太低，所以递归不是任何场景都适用的
//比如以下代码，求第40个斐波那契数，就要计算第三个斐波那契数三千九百多万次
#include <stdio.h>

int count = 0;

int Fib(int n)
{
    if (n == 3)
    {
        count++;
    }
    if (n <= 2)
    {
        return 1;
    }
    else
    {
        return Fib(n - 1) + Fib(n - 2);
    }
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = Fib(n);
    printf("%d\n", ret);
    printf("%d", count);
    return 0;
}

//迭代：
#include <stdio.h>

int Fib(int n)
{
    //a和b代表的是第一个和第二个斐波那契数
    int a = 1;
    int b = 1;
    int c = 1;

    //第一个斐波那契数和第二个斐波那契数是定死的，所以从第三个斐波那契数开始进入循环
    //例如求第三个斐波那契数，此时进入循环
    //c在第一次循环中表示第三个斐波那契数，就等于第一个斐波那契数（a）和第二个斐波那契数（b）之和
    //然后将b的值赋给a，表示新a，也就是此时的a表示第二个斐波那契数
    //再将c的值赋给b，表示新b，也就是此时的b表示第三个斐波那契数
    //最后n--，判断n是否大于或等于3，如果不满足条件，跳出循环，返回c的值
    //假设这里的n为4，那么n--，n变成3，再次进入循环
    //此时的a和b代表的就是第二个和第三个斐波那契数，同理进行运算
    while(n >= 3)
    {
        c = a + b;
        a = b;
        b = c;
        n--;
    }
    //如果输入的n小于3，就不进入循环，直接返回c的值：1
    return c;
}
int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = Fib(n);
    printf("%d", ret);
    return 0;
}
//迭代法就可以瞬间计算出结果，因为迭代没有重复计算
